package demo4;

import com.sun.java.swing.plaf.windows.WindowsDesktopIconUI;
import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
public class Solution {
    //1.完全二叉树的节点个数(剪枝)
    private int sum;
    public int countNodes(TreeNode root) {
        dfs(root);
        return sum;
    }
    private void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        //左树为空，右树一定为空，并且一定没有子代
        if(root.left == null) {
            sum += 1;
            return;
        }
        sum += 1;
        //递归的去看左树和右树
        dfs(root.left);
        dfs(root.right);
    }


    //2.最大二叉树(递归分治)
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return createTree(nums, 0, nums.length - 1);
    }
    private TreeNode createTree(int[] nums, int left, int right) {
        if(left > right) {
            return null;
        }
        //找出中间位置
        int mid = fundMaxNum(nums, left, right);
        //创建子树
        TreeNode root = new TreeNode(nums[mid]);
        //递归的创建左右子树
        root.left = createTree(nums, left, mid - 1);
        root.right = createTree(nums, mid + 1, right);
        return root;
    }
    //找出最大值
    private int fundMaxNum(int[] nums, int left, int right) {
        int index = left;//下标
        for(int i = left; i <= right; i++) {//注意这里是下标，所以要小于等于
            index = nums[i] > nums[index] ? i : index;
        }
        return index;
    }

    //3.找树左下角的值(队列：层序遍历)
    public int findBottomLeftValue(TreeNode root) {
        //层序遍历，找出最后一层
        //维护一个队列即可
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int prev = 0;//用来保存上一层的第一个结果
        TreeNode cur = root;
        while(!queue.isEmpty()) {
            int size = queue.size();//记录当前层的个数，便于出队
            prev = queue.peek().val;//记录这一层第一个元素
            while(size > 0) {
                TreeNode node = queue.poll();
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
        }
        return prev;
    }
    //4.二叉树的最近公共祖先(dfs)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        if(root == p || root == q) {
            return root;
        }
        //分别去递归左右子树去找
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //左树若为空，说明在右树上
        if(left == null) {
            return right;
        }
        if(right == null) {
            return left;
        }
        //都不为空，说明根节点就是
        return root;
    }
    //二叉搜索树的最近公共祖先
/*    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //若p,q一个大于跟结点一个小于跟结点，则跟结点就是
        //这里需要强转成long类型
        if((root.val - p.val)* 1L * (root.val - q.val) <= 0) {
            return root;
        }
        return lowestCommonAncestor(root.val > q.val ? root.left : root.right, p, q);
    }*/

    //5.剑指 Offer 34. 二叉树中和为某一值的路径(回溯剪枝)
    private List<List<Integer>> paths = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        //回溯剪枝
        backPrune(root, target);
        return paths;
    }
    private void backPrune(TreeNode root, int target) {
        if(root == null) {
            return;
        }
        //不不为空记录下路径
        path.add(root.val);
        //到了叶子结点，需要判断是否满足要求
        if(root.left == null && root.right == null) {
            if(target - root.val == 0) {
                paths.add(new ArrayList<>(path));
            }
        }
        //递归左右子树
        backPrune(root.left, target - root.val);
        backPrune(root.right, target - root.val);
        //左右子树完后需要剪枝
        path.remove(path.size() - 1);
    }
    //6.剑指 Offer 36. 二叉搜索树与双向链表
 /*   private Node prev;//记录前驱
    private Node head;//链表头节点
    public Node treeToDoublyList(Node root) {
        if(root == null){
            return root;
        }
        dfs(root);
        head.left = prev;
        prev.right = head;
        return head;
    }
    private void dfs(Node root) {
        if(root == null) {
            return;
        }
        dfs(root.left);
        if(prev != null) {
            root.left = prev;
            prev.right = root;
        }else {
            head = root;
        }
        prev = root;
        dfs(root.right);
    }
    //7.二叉树展开为链表
    private TreeNode right;//暂存右结点
    public void flatten(TreeNode root) {
        if(root == null) {
            return;
        }
        right = root.right;
        root.right = root.left;
        root.left = null;
        //将暂存的右节点接入到最右边
        TreeNode cur = root;
        while(cur.right != null) {
            cur = cur.right;
        }
        //连接
        cur.right = right;
        //递归下去
        flatten(root.left);
        flatten(root.right);
    }*/
    //8.二叉树的右视图
/*    public List<Integer> rightSideView(TreeNode root) {
        //层序遍历 + 双端队列(返回队尾)
        Deque<TreeNode> deque = new LinkedList<>();
        List<Integer> list = new LinkedList<>();
        if(root == null) {
            return list;
        }
        deque.offerFirst(root);
        while(!deque.isEmpty()) {
            int size = deque.size();
            int nowSize = size;//一个不变的size
            while(size > 0) {
                if(size == nowSize) {
                    list.add(deque.peekLast().val);
                }
                TreeNode node = deque.pollFirst();
                if(node.left != null) {
                    deque.offerLast(node.left);
                }
                if(node.right != null) {
                    deque.offerLast(node.right);
                }
                size--;
            }
        }
        return list;
    }*/
    //8.二叉树的右视图(DFS)
    private List<Integer> list = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        //DFS
        dfs(root, 0);
        return list;
    }
    private void dfs(TreeNode root, int depth) {
        if(root == null){
            return;
        }
        //若当前深度，list没有对应的数值，就存放进来
        if(depth == list.size()) {
            list.add(root.val);
        }
        //先递归右节点，再递归左节点，就能保证先拿到右结点（对应深度若没有右结点，就会放入左节点）
        dfs(root.right, depth + 1);
        dfs(root.left, depth + 1);
    }
    //9.二叉树的锯齿形层序遍历(双端队列)
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        //层序遍历 + 双端队列
        Deque<TreeNode> deque = new LinkedList<>();
        List<List<Integer>> ret = new LinkedList<>();
        if(root == null) {
            return ret;
        }
        boolean trend = true;//true表示从左向右遍历，false表示从右向左遍历
        deque.offerFirst(root);
        while(!deque.isEmpty()) {
            int size = deque.size();
            Deque<Integer> tmp = new LinkedList<>();
            while(size > 0) {
                TreeNode node = deque.pollFirst();
                //按照不通顺序入队，保证了之子形
                if(trend) {
                    tmp.offerLast(node.val);
                }else {
                    tmp.offerFirst(node.val);
                }
                if(node.left != null) {
                    deque.offerLast(node.left);
                }
                if(node.right != null) {
                    deque.offerLast(node.right);
                }
                size--;
            }
            trend = !trend;
            ret.add(new LinkedList<>(tmp));
        }
        return ret;
    }
    //10.二叉树的层序遍历 II(辅助队列)
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();
        if(root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new LinkedList<>();
            while(size > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
            //每次都放在开头，就可以保证是自下而上的了
            ret.add(0, list);
        }
        return ret;
    }
}














